monotonic ：單調，遞增或遞減

這是一個看起來很簡單的資料結構，
擁有 O(N) time complexity 的優秀特性，
但要能實際應用在問題裡卻不是很容易，
如果是用 heap 的題目，可以思考是否可以轉為使用 monotonic stack。

Time Complexity: O(N)

優點：linear time complexity
所有的元素最多只會進去一次，也最多只會出去一次。

性質 / 題型特徵

1. Monotonic

2. 元素 push 上 stack 前，會把破壞此 stack 單調性質（遞增或遞減）的元素移除。（LIFO）

3. 可以找到目前元素向左看（for all i < current_i）第一個比他小 / 大的元素

   • 往左看 就是 「已遍歷」、「目前為止」的感覺
   • 已遍歷中「最靠近」目前元素 and 符合某條件的元素

4. 可以找到 目前為止最大的數

   • 「往左看比目前元素大 and 按序（遞減）排列」元素們
   • 往左看比目前元素大
     -> 得到比現元素大的已遍歷元素 or 現元素（代表沒有比較大的數）
     -> 得到 目前為止最大的數
   • 照順序遞減排列 -> 不怕第一大被刪除，我還知道第二大是誰。
   • [[239. Sliding Window Maximum]]

5. 某些元素因為不符合和現元素相比的某個條件，在未來不會被用到了，可被捨棄。

6. 某些元素被捨棄時，可能是答案。[[1944. Number of Visible People in a Queue]]

遞增: 找第一個左小

• 找到 左邊第一個比目前元素小 的元素。

一個遞增的 monotonic stack，新增 a 進去，top 為頂元素。

1. a > top，可以直接 push
   此時因為 monotonic，top 為 a 左邊第一個比 a 小的數
2. a < top，為了維持 monotonic，要 pop 直到以下兩種情形才能 push a：
   1. pop 到 a > top
   2. stack empty

• 若 pop 到 a > top，就是回 去 step 1. 的情形。
• 若 stack 先空掉，則對 a 來說左邊沒有比較小的數

對這些被 pop 的元素來說，a 是在他們右側第一個比他們小的元素

遞減: 找第一個左大

• 找到 左邊第一個比目前元素大 的元素。

1. a < top，合法直接放
   top 為 a 左邊第一個比 a 大的數